#include <stdio.h>
#include <stdlib.h>

#define FLAG -100

typedef int DataType;
typedef enum bool Bool;
enum bool {
        false, true
};

struct LinkedList {
        DataType val;
        struct LinkedList *next;
};
typedef struct LinkedList *LinkedList;
typedef struct LinkedList *PNode;

struct LinkedSet {
        LinkedList ptrlist;
        int len;
};
typedef struct LinkedSet *LinkSet;

LinkSet createEmptySet(void);
Bool isEmptySet(LinkSet head);
PNode Locate_Set(LinkSet head, DataType x);
// int Set_Length(LinkSet head);
void InsertPost_Set(PNode p, DataType x);
void DeleteAddress_Set(LinkSet head, PNode p);
LinkSet Set_Intersection(LinkSet head1, LinkSet head2);
LinkSet Set_Union(LinkSet head1, LinkSet head2);
LinkSet Set_Difference(LinkSet big, LinkSet small);
Bool Set_Is_Equal(LinkSet head1, LinkSet head2);
Bool Set_Is_Subset(LinkSet big, LinkSet small);
LinkSet createLinkSet_H(void);
void print_Set(LinkSet S);
void destory_Set(LinkSet S);

// 创建带头结点的链式集合.
LinkSet createEmptySet(void)
{
        LinkSet head = (LinkSet)malloc(sizeof(struct LinkedSet));
        head->ptrlist = (LinkedList)malloc(sizeof(struct LinkedList));
        if (head == NULL) {
                printf("Out of memory!\n");
                return head;
        }
        head->ptrlist->next = NULL;
        head->len = 0;
        return head;
}

Bool isEmptySet(LinkSet head)
{
        return head->ptrlist->next == NULL;
}

// 判断x是否为集合的成员.
// 时间复杂度：O(n), 空间复杂度：O(1).
PNode Locate_Set(LinkSet head, DataType x)
{
        PNode p;
        for (p = head->ptrlist->next; p != NULL; p = p->next)
        {
                if (x == p->val)
                        return p;
        }
        return p;
}

// 求解集合的长度.
// 时间复杂度：O(n), 空间复杂度：O(1).
/* int Set_Length(LinkSet head)
{
        LinkSet p;
        int length = 0;
        for (p = head->next; p != NULL; p = p->next)
                length++;
        return length;
} */

void InsertPost_Set(PNode p, DataType x)
{
        PNode q = (PNode)malloc(sizeof(struct LinkedList));
        if (q == NULL) {
                printf("Out of memory!\n");
        }
        q->val = x;
        q->next = p->next;
        p->next = q;
}

void DeleteAddress_Set(LinkSet head, PNode p)
{
        PNode q = head->ptrlist;
        while (q->next != p && q->next != NULL)
                q = q->next;
        if (q->next == NULL) {
                printf("Not find it!\n");
        } else {
                PNode tmp = p;
                q->next = q->next->next;
                free(tmp);
        }
}

// 求交集.
LinkSet Set_Intersection(LinkSet head1, LinkSet head2)
{
        LinkSet head3;
        head3 = createEmptySet();
        // 使用双重for循环来查找相同元素.
        PNode p, q;
        for (p = head1->ptrlist->next; p != NULL; p = p->next) {
                for (q = head2->ptrlist->next; q != NULL; q = q->next) {
                        if (p->val == q->val) {
                                InsertPost_Set(head3->ptrlist, p->val);
                                head3->len++;
                                break;
                        }
                }
        }
        return head3;
}

// 求并集. 时间复杂度：O(n^2), 空间复杂度: O(n), 和新开辟的集合长度有关.
// 将集合A复制给集合C，集合B进来C时进行判断，如果C已经有了，就不插入，否则插入之.
LinkSet Set_Union(LinkSet head1, LinkSet head2)
{
        LinkSet head4;
        head4 = createEmptySet();
        PNode p, q = head4->ptrlist;
        // 将A中所有元素复制给C.
        for (p = head1->ptrlist->next; p != NULL; p = p->next) {
                InsertPost_Set(q, p->val);
                head4->len++;
                q = q->next;
        }
        // 将B中和C中不同元素插入
        for (p = head2->ptrlist->next; p != NULL; p = p->next) {
                for (q = head4->ptrlist->next; q != NULL; q = q->next) {
                        if (p->val == q->val) {
                                goto Flag1;
                        }
                }
                InsertPost_Set(head4->ptrlist, p->val);
                head4->len++;
Flag1:;
        }
        return head4;
}

// 求差集. 时间复杂度：O(n^2), 空间复杂度: O(n), 和新开辟的集合长度有关.
LinkSet Set_Difference(LinkSet big, LinkSet small)
{
        LinkSet head5;
        head5 = createEmptySet();
        PNode p, q = head5->ptrlist;
        // 将A中所有元素复制给C.
        for (p = big->ptrlist->next; p != NULL; p = p->next) {
                InsertPost_Set(q, p->val);
                q = q->next;
        }
        // 删除C中和B相同的元素.
        for (p = head5->ptrlist->next; p != NULL; p = p->next) {
                for (q = small->ptrlist->next; q != NULL; q = q->next) {
                        if (p->val == q->val) {
                                DeleteAddress_Set(head5, p);
                        }
                }
        }
        return head5;
}

// 先求出head1和head2两集合的并集，在分别判断并集和这两个集合是否相等.
// 若不相等，则false；反之，则true.
Bool Set_Is_Equal(LinkSet head1, LinkSet head2)
{
        // 对长度进行判断
        if (head1->len != head2->len) {
                return false;
        }
        /* printf("1 break\n");
        exit(1); */
        LinkSet head6 = Set_Union(head1, head2);
        /*print_Set(head6);
        printf("head1-len=%d\nhead2-len=%d\nhead6-len=%d\n", head1->len, head2->len, head6->len);
        exit(1); */
        // 对长度进行判断
        if (head1->len != head6->len || head2->len != head6->len) {
                destory_Set(head6);
                return false;
        }
        /* printf("1 break\n");
        exit(1); */
        PNode p, q;
        for (p = head6->ptrlist->next; p != NULL; p = p->next) {
                for (q = head1->ptrlist->next; q != NULL; q = q->next) {
                        // printf("p=%d\nq=%d\n", p->val, q->val);
                        if (p->val == q->val) {
                                goto Flag2;
                        }
                }
                destory_Set(head6);
                return false;
Flag2:;
        }
        for (p = head6->ptrlist->next; p != NULL; p = p->next) {
                for (q = head2->ptrlist->next; q != NULL; q = q->next) {
                        if (p->val == q->val) {
                                goto Flag3;
                        }
                }
                destory_Set(head6);
                return false;
Flag3:;
        }
        /* printf("1 break\n");
        exit(1); */
        destory_Set(head6);
        return true;
}

Bool Set_Is_Subset(LinkSet big, LinkSet small)
{
        if (big->len < small->len) {
                return false;
        }
        LinkSet head7 = Set_Union(big, small);
        /* printf("head7:\n");
        print_Set(head7); */
        if (Set_Is_Equal(big, head7)) {
                destory_Set(head7);
                /* printf("error!");
                exit(1); */
                return true;
        }
        /* printf("stop!\n");
        exit(1); */
        destory_Set(head7);
        return false;
}

// 头插法建立空集合.
LinkSet createLinkSet_H(void)
{
        LinkSet head = createEmptySet();
        int x, tmp = 0;
        scanf("%d", &x);
        while (x != FLAG) {
                PNode p = (PNode)malloc(sizeof(struct LinkedList));
                p->val = x;
                tmp++;
                p->next = head->ptrlist->next;
                head->ptrlist->next = p;
                scanf("%d", &x);
        }
        head->len = tmp;
        return head;
}

void print_Set(LinkSet S)
{
        PNode p = S->ptrlist->next; // 指向第一个元素.
        while (p != NULL) {
                printf("%d ", p->val);
                p = p->next;
        }
        printf("\n");
}

void destory_Set(LinkSet S)
{
        if (isEmptySet(S)) {
                return ;
        }
        // p为快指针，q为慢指针.
        PNode p, q;
        p = S->ptrlist->next->next;
        q = S->ptrlist->next;
        while (p != NULL && p->next != NULL) {
                PNode tmp = q->next;
                free(q);
                p = p->next->next;
                q = tmp;
        }
        free(S->ptrlist);
        free(S);
}

int main()
{
        LinkSet S = createLinkSet_H();
        int x;
        if (isEmptySet(S)) {
                printf("This set is empty.\n");
        } else {
                printf("This set is not empty.\n");
        }

        printf("请问您想查找哪个元素呢？");
        scanf("%d", &x);
        PNode p = Locate_Set(S, x);
        if (p != NULL && p->val == x) {
                printf("找到了!\n");
        } else {
                printf("没找到。\n");
        }
        printf("请问您想插入哪个元素呢？");
        scanf("%d", &x);
        InsertPost_Set(S->ptrlist, x);
        print_Set(S);
        printf("让我们删除一个元素吧!\n");
        printf("请先输入一个集合中想删除的元素值:");
        scanf("%d", &x);
        p = Locate_Set(S, x);
        if (p != NULL) {
                DeleteAddress_Set(S, p);
        }
        print_Set(S);

        printf("请创建两个集合\n");
        LinkSet S4 = createLinkSet_H();
        // getchar();
        LinkSet S5 = createLinkSet_H();
        // getchar();
        LinkSet S1 = Set_Intersection(S4, S5);
        printf("这两个集合的交集为：\n");
        print_Set(S1);
        LinkSet S2 = Set_Union(S4, S5);
        printf("这两个集合的并集为：\n");
        print_Set(S2);
        LinkSet S3 = Set_Difference(S4, S5);
        printf("这两个集合的差集为：\n");
        print_Set(S3);

        printf("请创建两个集合\n");
        LinkSet S6 = createLinkSet_H();
        // getchar();
        LinkSet S7 = createLinkSet_H();
        // getchar();
        if (Set_Is_Equal(S6, S7)) {
                printf("这两个集合是相等的.\n");
        } else {
                printf("这两个集合是不相等的.\n");
        }
        if (Set_Is_Subset(S6, S7)) {
                printf("第二个集合是第一个集合的子集.\n");
        } else {
                printf("第二个集合不是第一个集合的子集.\n");
        }
        if (Set_Is_Subset(S7, S6)) {
                printf("第一个集合是第二个集合的子集.\n");
        } else {
                printf("第一个集合不是第二个集合的子集.\n");
        }
        // 最后记得free所有malloc的东西.
        // destory(S, S1, S2, S3, S4, S5, S6, S7);
        destory_Set(S);
        destory_Set(S1);
        destory_Set(S2);
        destory_Set(S3);
        destory_Set(S4);
        destory_Set(S5);
        destory_Set(S6);
        destory_Set(S7);
        return 0;
}